package Experiment3;

import java.nio.ShortBuffer;
import java.util.Iterator;
import java.util.Scanner;

import edu.princeton.cs.algs4.*;

/**
 * 基于{@code MyDijkstra}求解给定图的单个最短路径问题
 * 
 * @author Chen Junjie
 */
public class ShortestPath {
    private MyDijkstra dij_sp;
    private int destination_point;
    private int source_point;
    private EuclidienGraph graph;
    
    public ShortestPath(EuclidienGraph graph,int source_point,int destination_point){
        this.destination_point=destination_point;
        this.source_point=source_point;
        this.graph=graph;
        dij_sp=new MyDijkstra(graph);
        dij_sp.calculateShortPath(source_point, destination_point);
        printResults();
    }

    private void printResults(){
        if(!dij_sp.hasPath()){
            System.out.println("No Path");
            return;
        }
        
        System.out.print("DISTANCE:"+dij_sp.distance()+"  "+"PATH:");
        
        Iterator<Edge> it=dij_sp.path().iterator();
        int current_node=source_point;
        while(it.hasNext()){
            System.out.print(current_node);
            System.out.print("->");
            current_node=it.next().other(current_node);
        }
        System.out.println(destination_point);
        new DrawPath(dij_sp.path()).draw();
    }

    public double getDistance(){
        return dij_sp.distTo(destination_point);
    }

    public boolean hasPath(){
        return dij_sp.hasPathTo(destination_point);
    }

    public void printDistance(){
        System.out.printf("%.2f",getDistance());
    }

    public void printPath(){
        Iterable<Edge> path=dij_sp.pathTo(destination_point);
        Iterator<Edge> it=path.iterator();
        int current_node=source_point;
        while(it.hasNext()){
            System.out.print(current_node);
            System.out.print("->");
            current_node=it.next().other(current_node);
        }
        System.out.print(destination_point);
    }

    private class DrawPath{
        private double max_width;
        private double max_height;

        private double min_x;
        private double min_y;
        
        public DrawPath(Iterable<Edge> path){
            max_width=0;
            max_height=0;

            double max_x=0;
            double max_y=0;
            min_x=Double.POSITIVE_INFINITY;
            min_y=Double.POSITIVE_INFINITY;

            for(Edge e:path){
                int v=e.either();
                int w=e.other(v);
                double x=graph.getPoint(v).x();
                double y=graph.getPoint(v).y();
                if(x>max_x) max_x=x;
                if(y>max_y) max_y=y;
                if(x<min_x) min_x=x;
                if(y<min_y) min_y=y;
                x=graph.getPoint(w).x();
                y=graph.getPoint(w).y();
                if(x>max_x) max_x=x;
                if(y>max_y) max_y=y;
                if(x<min_x) min_x=x;
                if(y<min_y) min_y=y;
            }
            max_height=max_y-min_y;
            max_width=max_x-min_x;

            max_width+=max_width*0.2;
            max_height+=max_height*0.2;

        }

        private double getX(int point){
            return (graph.getPoint(point).x()-min_x)/max_width;
        }

        private double getY(int point){
            return (graph.getPoint(point).y()-min_y)/max_height;
        }


        public void draw(){
            Iterable<Edge> path=dij_sp.pathTo(destination_point);
            Iterator<Edge> it=path.iterator();
            int current_node=source_point;
            int last_node=-1;
            StdDraw.setCanvasSize(720, 720);
            StdDraw.setPenRadius(0.003);
            StdDraw.setPenColor(StdDraw.BLACK);
            if(source_point!=destination_point) {
                StdDraw.text(getX(source_point), getY(source_point), "source");
            }
            while(it.hasNext()){
                if(last_node>=0){
                    StdDraw.line(getX(last_node),getY(last_node),getX(current_node),getY(current_node));
                }
                StdDraw.point(getX(current_node), getY(current_node));
                last_node=current_node;
                current_node=it.next().other(current_node);
            }
            if(last_node>=0){
                StdDraw.line(getX(last_node),getY(last_node),getX(current_node),getY(current_node));
            }
            StdDraw.setPenRadius(0.005);
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.point(getX(destination_point), getY(destination_point));
            StdDraw.setPenColor(StdDraw.BLACK);
            StdDraw.text(getX(destination_point), getY(destination_point), "destination");
            StdDraw.show();
        }
    }

    

    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        System.out.print("输入地图:");
        String data=sc.next();
        System.out.print("输入起点:");
        int source=sc.nextInt();
        System.out.print("输入终点:");
        int destination=sc.nextInt();
        ShortestPath shortest_path=new ShortestPath(new InputData(data).getGraph(), source, destination);
        sc.close();
    }
}
